package gold.digger;

import gold.vo.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC865 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        private TreeNode res = null;
        private int maxlevel = Integer.MIN_VALUE;

        public TreeNode subtreeWithAllDeepest(TreeNode root) {
            dfs(root, 1);
            return res;
        }

        // 后续遍历
        private int dfs(TreeNode root, int level) {
            if (root == null) {
                return level - 1;
            }
            int left = dfs(root.left, level + 1); // 左子树的最大深度
            int right = dfs(root.right, level + 1);// 右子树的最大深度
            int d = Math.max(left, right);//

            maxlevel = Math.max(maxlevel, d); // 更新最大深度

            if (left == right && left == maxlevel) {// 如果左右子树最大深度相等，且等于最大深度
                res = root;
            }
            return d;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC865 an = new LC865();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
